Masala #R089H

Xotira 128 MB Vaqt 1000 ms Qiyinchiligi 48 %

#Dinamik dasturlash

#Matrix

#Prefix Sum

#Binary Indexed Tree

Muallif: Murodullayev Anvarjon

Parallelpiped Sum

Sizga elementlari soni cheksiz bo'lgan uch o'lchovli \(a\) massiv berilgan. Massiv quyidagi tardibda to'ldiriladi.

\(i,j,k\) indekslardan kamida bittasi \(0\) ga teng bo'lsa: \(a[i,j,k] = 0\).
\(i,j,k\) indexlarning barchasi tub son bo'lsa: \(a[i,j,k] = i*j*k\).
Massivning qolgan barcha elementlari uchun \(a[i,j,k] = i + j + k\).

Massivni to'g'ri burchakli parallelpiped shaklida tasavvur qiling.
Sizga \(q\) ta so'rovda \(a\) massivning ixtiyoriy 2 ta elementi koordinatalari beriladi. Qarama-qarshi uchlari shu koordinatada bo'lgan parallelpiped (qism massiv) elementlari yig'indisini toping.

Kiruvchi ma'lumotlar:

Dastlabki satrda \(q(q \le 10^5)\) so'rovlar soni kiritiladi.
Keyingi \(q\) ta qatorda mos ravishda oltitadan son \(i_1,j_1,k_1,i_2,j_2,k_2(1 \le i_1,j_1,k_1,i_2,j_2,k_2 \le100)\), qism massiv qarama-qarshi uchlarining koordinatalari kiritiladi.

Chiquvchi ma'lumotlar:

Har so'rov uchun mos ravishda, alohida satrlarda qism massiv elementlari yig'indisini chop eting.

Misollar

#	input.txt	output.txt
1	3 1 1 1 3 3 3 3 3 3 1 1 1 1 3 1 3 1 3	227 227 227
2	8 25 71 53 15 19 25 34 39 32 84 38 10 5 43 86 69 83 43 49 10 14 46 42 70 76 89 10 81 68 26 84 82 19 87 32 39 51 10 47 13 39 34 63 76 4 63 20 81	11362198 278001 246747978 6329856 2978350 734706 10630620 682461

input.txt

output.txt

3
1 1 1 3 3 3
3 3 3 1 1 1
1 3 1 3 1 3

227
227
227

8
25 71 53 15 19 25
34 39 32 84 38 10
5 43 86 69 83 43
49 10 14 46 42 70
76 89 10 81 68 26
84 82 19 87 32 39
51 10 47 13 39 34
63 76 4 63 20 81

Izoh:

Kiritish va chiqarishni tezlashtirish uchun faylli oqimdan foydalanish tavsiya etiladi

Python dasturlash tilida ishlaydiganlar uchun pypy kompulyatoridan foydalanish tavsiya etiladi.

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin